\part{Algebraic number theory, Ideal lattices, Fully homomorphic encryption}

\section{Algebraic number theory and Ideal lattices}

\subsection{Cyclotomic fields and rings}

\begin{definition}
A primitive $n^{th}$ root of unity is an element of $\mathbb{C}^*$ of exact order $n$, namely $e^{\frac{2 i \pi k}{n}}$, where $(k,n)=1$.
\end{definition}

\begin{definition}
The $n^{th}$ cyclotomic polynomial $\Phi_n$  is $\Phi_n(X) = \Pi_{S \ prime \ n^{th} \ root \ of \ 1} (X-S)=\Pi_{(k,n)=1, 1 \leq k \leq n} (X - e^{\frac{2 i k \pi}{n}})$
$S_n=e^{\frac{2 i \pi}{n}}$
\end{definition}

\textbf{Check the ex with Hugo Feree}

rem: def $\Phi_n=phi(n)$
$\phi(n)=n \Pi_{p|n} (1-\frac{1}{p})$

($p$ is prime)

\begin{proposition}
$\Phi_n(X) \in \mathbb{Z}[X]$, monic.
\end{proposition}

\begin{proof}
\begin{lemm}
$X^n-1=\Pi_{d | n} \Phi_d(X)$
\end{lemm}
\begin{proof}
$X^n-1=\Pi_k (X-S_n^k)$
$k = k_1 k_2$, where $k_1=(k,n)$. $(k_2,n)=1$ $k_2=\frac{k}{k_1}$
Then $X^n-1= \Pi_{k_1 | n} \Pi_{1 \leq k_2 \leq \frac{n}{k_1}, (k_2,n)=1} (X-S_n^{k_1 k_2})$
$\Phi_{\frac{n}{k_1}}(X)=\Pi_{1}$
 \textbf{Proof here, check that with Hugo Feree}
\end{proof}
By induction, $\Phi_1(X)$
$\Phi_n(X)=\frac{X^n-1}{\Pi_{d | n d \neq n} \Phi_d(X)}$
By induction, $\Pi_{d | n, d \neq n} \Phi_d(X) \in \mathbb{Z}[X]$+monic.

The quotient of two monic polynomials with integer coefficients is monic, with integer coefficients.
\end{proof}

\begin{proposition}
$\Phi_n(X)$ is an irreducible polynomial over $\mathbb{Q}$
\end{proposition}
\begin{proof}
Admitted
\end{proof}

\begin{definition}
The $n^{th}$ cyclotomic field over $\mathbb{Q}$ is

$\mathbb{Q}(S_n)=\mathbb{Q}[x]/(\Phi_n(x)):=K_n$ (The first equality comes from the irreducibility of $\Phi_n$)
\end{definition}

Computationnally speaking, the representation is the most convenient.
\begin{itemize}
\item An element of $K_n$ is a polynomial with rationnal coeff. of degree $< n$
\item Addition is ordinary. Polynomial addition.
\item Mult is ordinary too, is polynomial mod $\Phi_n(X)$.
\item Inversion is doing the extended Euclidean algorithm on $p$ and $\Phi_n$ $P(X)U(X)+\Phi_n(X)V(X)=1$ (since $\Phi_n$ is irreducible) $\rightarrow P(X)U(X)=1 mod (\Phi_n(X))$
\end{itemize}

Rem: $P(X)$ corresponds to $P(S_n) \in \mathbb{Q}(S_n)$
Rem: $K_n$ has a $\mathbb{Q}$-vector space structure with dimension $\phi(n)$ 

\begin{definition}
The \textbf{ring} of integers $O_{K_n}$ of $K_n$ is $\mathbb{Z}[S_n]=\mathbb{Z}[X]/(\Phi_n(X))$
\end{definition}

Rem: $O_{K_n}$ is a free $\mathbb{Z}$-module with rank $\phi(n)$, with basis $1,S_n,...,S_n^{\phi(n)-1}$
Elements of $O_{K_n}$ are called \textbf{algebraic integers}.

\subsection{Plongements, trace et norme} (plongement = embedding)

\begin{definition}
Les plongements de $K_n$ dans $\mathbb{C}$ sont définis par: 

$\sigma_k: K_n \rightarrow \mathbb{C}$ 

$\sum_{i=0}^{\phi(n)-1} x_i (\zeta)^i \mapsto \sum_{i=0}^{\phi(n)-1} x_i K^{ki} $ (où $(k,n)=1$)
\end{definition}

Dans le cas présent, ce sont des automorphismes de $K_i$, l'ensemble de ces automorphismes forme un groupe $Gal(K_n,\mathbb{Q})$.

Rem: L'image d'un entier algébrique par $\sigma_k$ est un entier algébrique.

But: Réaliser $O_{K_n}$ (et ses idéaux) comme sous-ensemble de $\mathbb{R}^d$.

Méthode 1: "coordinate embedding"
$\theta: K_n \rightarrow \mathbb{R}^{\phi(n)}$

$\sum_{i=0}^{\phi(n)-1} x_i \zeta^i \mapsto (x_0,...,x_{\phi(n)-1})$ (où $x_i \in \mathbb{Q}$)

\begin{proposition}
$\Theta(O_{K_n})=\mathbb{Z}^{\phi(n)}$ est un réseau de rang $\phi(n)$, de volume 1.
\end{proposition}
Méthode 2: Plongement $T_2: K_n \rightarrow \mathbb{R}^{\phi(n)}$

$x \mapsto (Re \sigma_1(x), Im \sigma_1(x),Re \sigma_2(x),...., Re \sigma_{\frac{\phi(n)}{2}}, Im \sigma_{\frac{\phi(n)}{2}})$

\begin{proposition}
$T_2(O_{K_n})$ est un réseau de rang $\phi(n)$. Son volume est appelé (au signe près) \textbf{discriminant de $K_n$} et noté $\Delta_{K_n}$.
\end{proposition}

On a $\Delta_{K_p}=p^{p-1}[(-1)^{\frac{p-1}{2}}]$ $p \in \mathbb{P}$

$\Delta_{K_n}=\frac{n}{2}^{\frac{n}{2}}, n=2^k$

\begin{definition}
$x \in K_n$, $x$ induit.

$m_x \in L_{\mathbb{Q}}(K_n):=$ appl $\mathbb{Q}$-linéaire sur $K_n$

$m_x : K_n \rightarrow K_n$

$y \mapsto xy$
\begin{itemize}
\item $Tr_{K/\mathbb{Q}}^-(x)=Tr(m_x)$
\item $N_{K/\mathbb{Q}}(x)=det(m_x)$
\item $\chi_{K/\mathbb{Q}}(x)=det(X I_{\phi(n)}-m_x)$
\end{itemize}
\end{definition}

\begin{proposition}
$Tr(x+y)=Tr(x)+Tr(y)$

$N(xy)=N(x)+N(y)$
\end{proposition}

\begin{theorem}
$Tr_{K/\mathbb{Q}}(x)=\sum \sigma_i(x)$

$N_{K/\mathbb{Q}}(x)=\Pi \sigma_i(x)$

$\chi_{K/\mathbb{Q}}(x)=\Pi(X-\sigma_i(x))$
\end{theorem}

\begin{corollary}
$Tr_{K_p/\mathbb{Q}}(\zeta_p)=\sum_{k=1}^{p-1} \sigma_k(\zeta)=\sum_{k=1}^{p-1} \zeta^k=-1$ (Somme des racines de $\Phi_p(X)=X^{p-1}+X^{p-2}+...+1$)

$Tr_{K_{2^n}/\mathbb{Q}}(\zeta_{2^n})=0$ (Somme des racines de $\Phi_{2^n}(X)=X^{2^{n-1}}+1$)

$N_{K_p/\mathbb{Q}}(\zeta_p)=(-1)^{p-1}.1=1$ ($p >2$, $p \in \mathbb{P}$)
\end{corollary}

Exercise: $N_{K_p/\mathbb{Q}}(1-\zeta_p)$

\begin{proposition}
Si $x \in O_{K_n}$,

$Tr(x), N(x) \in \mathbb{Z}$
\end{proposition}

\subsection{Idéaux}

\begin{definition}
Un idéal entier de $O_{K_n}$ est un sous-groupe additif $I$ de $O_{K_n}$ tel que $\forall a \in O_{K_n}, \forall x \in I, a x \in I$
\end{definition}

Ex: Idéal principal.

$x \in O_{K_n}$, l'ensemble $x O_{K_n}$ est un idéal, appelé idéal principal engendré par x.

\begin{definition} (Somme de deux idéaux)
Si $I$ et $J$ sont deux idéaux entiers, $I+J=\{i+j, i \in I, j \in J\}$ est un idéal entier.
\end{definition}

\begin{definition} (Produit de deux idéaux)
Si $I$ et $J$ sont deux idéaux entiers,
$I J= \{ i_1 j_1+ i_2 j_2+...+ i_k j_k, (i_l,j_l) \in I*J \forall l \}$ est un idéal entier de $O_{K_n}$
\end{definition}

\begin{proposition}
Soit $I$ un idéal entier. Alors $O_{K_n}/I$ est \textbf{fini}. Son cardinal est la norma de $I$, notée $N(I)$
\end{proposition}

\begin{proof}
Soit $x \in I$.

$N_{K / \mathbb{Q}}(x)= \sigma_1(x) \sigma_2(x).. \sigma_k(x) \in I$ ($\sigma_1(x)=x$)

$\Rightarrow N_{K/\mathbb{Q}}(x) O_{K_n} \subset I$

$\Rightarrow O_{K_n}/I \subset O_{K_n}/ (N_{K/\mathbb{Q}}(x) O_{K_n})$ (isomorphe à $\mathbb{Z}^{phi(n)}$, $N_{K/\mathbb{Q}}(x)=u \in \mathbb{Z}$).

$O_{K_n}/I \subset \mathbb{Z}^{phi(n)}/u \mathbb{Z}^{phi(n)}$ (isomorphe à $(\mathbb{Z}/u \mathbb{Z})^{\phi(n)}$).

Donc $|O_{K_n}/I|<$ \textbf{infinity}
\end{proof}

\begin{proposition}
$I$, $J$ deux idéaux entiers. Alors 

$N(IJ)=N(I) N(J)$, 

$I=x O_{K_n}$, 

$N(I)=|N(x)|$
\end{proposition}

\begin{theorem}
I idéal entier. Alors $O(I)$ (resp. $T_2(I)$) est un réseau de $\mathbb{Z}^{\phi(n)}$ de volume $N(I)$ (resp. $N(I) \sqrt{|\Delta_k|}$)
\end{theorem}

\textbf{Important: plus haut, $\Delta_k$ est le carré du volume de $O_{K_n}$ dans $T_2$}

\begin{definition}
Un idéal fractionnaire est un sous-groupe additif $I$ de $O_{K_n}$ tel qu'il existe $d \in \mathbb{Z}-\{ 0 \}$ avec $d I$ idéal entier de $O_{K_n}$.
\begin{itemize}
\item Somme et produit d'idéaux s'étendent à ce cas
\item $N(I)=N(d I)/d^{\phi(n)}$ où $d$ est un entier tel que $dI$ idéal entier de $O_{K_n}$. $N(I) \in \mathbb{Q}$. 
\end{itemize}
\end{definition}

\begin{theorem}
Tout idéal fractionnaire $I (\neq \{ 0 \})$ est inversible, ie $\exists J$ idéal fractionnaire tel que $I J = O_{K_n}$. ($J=I^{-1}=\{y \in K_n / yI \subset O_{K_n} \}$)
\end{theorem}

\subsection{Idéaux premiers, décompositions}

\begin{definition}
Un idéal entier premier est un idéal entier $I$ de $O_{K_n}$ tel que $x y \in I \Rightarrow x \in I$ ou $y \in I$
\end{definition}

De façon équivalente, $O_{K_n}/I$ est un anneau intègre.

\begin{definition}
Un idéal entier $I \neq O_{K_n}$ est \textbf{maximal} si $\forall J$ idéal entier, $I \subset J \Rightarrow J=O_{K_n}$ ou $J=I$. De façon équivalente, $O_{K_n}/I$ est un corps.
\end{definition} 

\begin{proposition}
$I$ ($\neq O_{K_n}$) idéal entier. Alors $I$ premier $\Leftrightarrow$ $I$ maximal.
\end{proposition}

\begin{proof}
Anneau intègre fini $\Leftrightarrow$ corps fini
\end{proof}

\begin{theorem}
Tout idéal de $O_{K_n}$ s'écrit de manière unique, à l'ordre des facteurs près, sous la forme $\Pi_{i=1,r} \beta_i^{\alpha_i}$, $\alpha_i \in \mathbb{Z}, \beta_i$ idéal entier premier

Un tel idéal est entier ssi $\alpha_i \geq 0 \forall i$
\end{theorem}

\begin{corollary}
$I |J \Leftrightarrow J \subset I$ (où $I|J \Leftrightarrow \exists I', I I'=J$)
\end{corollary}

\begin{definition}
Soit $\mathfrak{P}$ idéal premier de $O_{K_n}$.

Alors $\mathfrak{P} \cap \mathbb{Z}$ est un idéal premier de $\mathbb{Z}$, ie $\beta \cap \mathbb{Z}= p \mathbb{Z}$.

$\mathbb{Z}/p \mathbb{Z} = O_{K_n} \cap \mathbb{Z}/ \mathfrak{P} \cap \mathbb{Z} \subset O_{K_n}/ \mathfrak{P}$

Sonc $O_{K_n}/ \mathfrak{P}$ est un corps fini de caractérisitique $p$, donc de la forme $CTF(p^k), k|\phi(n)$

En particulier, $p \in \mathfrak{P} \Rightarrow p O_{K_n} \subset \mathfrak{P} \Rightarrow \mathfrak{P} | p O_{K_n}$.

Pour décrire les idéaux prmeiers, il faut étudier la factorisation des idéaux $p O_{K_n}$
\end{definition}

Soit $p$ premier, $\exists e_i \in \mathbb{N}^*$, $\mathfrak{P}_i$ idéaux premiers tels que
$p O_{K_n} = \Pi_{i=1}^{r} \mathfrak{P}_i^{e_i}$

\begin{proposition}
$p^{f_i}:=N \mathfrak{P}_i$
\begin{itemize}
\item Alors $f_i=f$ ne dépend pas de $i$.
\item $e_i=e$ ne dépend pas de $i$.
\end{itemize}

Donc $p O_{K_n}=(\Pi_{i=1}^{r} \mathfrak{P}_i)^e$, avec $e f r= \phi(n)$.
$p$ est dit ramifié si $e > 1$; c'est équivalent à $p | n$.
\end{proposition}

\begin{theorem}
On suppose que
$\Phi_n(X)=\Pi_{i=1}^{r} T_i^{e_i}(X)$ (mod p)
est la factorisation de $\Phi_n(X) mod p$.

Alors, $\mathfrak{P}_i= T_i(\zeta) O_{K_n}+p O_{K_n}$ est un idéal premier de norme $p^{deg T_i}$, et $p O_{K_n} = \Pi_{i=1}^{r} \mathfrak{P}_i^{e_i}$
\end{theorem}

\begin{proof}
$N \mathfrak{P} = p^f \Rightarrow \mathfrak{P}$ est un idéal premier de degré $f$.
\end{proof}

\begin{corollary}
p ne divise pas n; $w=$ l'ordre de $p$ modulo $n$. $=inf\{ k >0 / p^k$ congru à$1 mod n \}$
Alors $p O_{K_n}=\Pi_{i=1}^{\phi(n)/w} \mathfrak{P}_i$, $f(\mathfrak{P}_i)=w$
\end{corollary}

Rm: Tout idéal est de la forme $k O_{K_n}+ \alpha O_{K_n}, k \in \mathbb{Z}, \alpha \in K_n$

\subsection{FFT (Fast Fourier Transform)}

Principe: On va faire de la crypto en utilisant des idéaux (presque) principaux.
\begin{itemize}
\item Représentation $O(n)$
\item Calcul= produit de 2 éléments de $O_{K_n}$; $O(n log n)$
\end{itemize}

$z_1 = \sum_{i=0}^{\phi(n)-1} z_{1,i} \zeta^i \mapsto^{DFT} (\sigma_k(z_1))_{i\le k \le n \\ (k, n)=1}$

$z_2 = \sum_{i=0}^{\phi(n)-1} z_{2,i} \zeta^i \mapsto^{DFT} (\sigma_k(z_2))_{i\le k \le n \\ (k, n)=1}$

$(\sigma_k(z_1).\sigma_k(z_2))_{1\le k \le n \\ (k, n)=1} = (\sigma_k(z_1.z_2))_{1\le k \le n \\ (k, n)=1}$ ($n$ multiplications)

$(\sigma_k(z_1.z_2))_{1\le k \le n \\ (k, n)=1} \mapsto^{DFT^{-1}} z_1.z_2$

Coût total de $z_1.z_2$:
\begin{itemize}
	\item $2$ $DFT$
	\item $1$ $DFT^{-1}$
	\item $n$ multiplications
\end{itemize}

Comment calculer $DFT$ rapidement ? Via l'algorithme $FFT$.

$FFT_n(Z(X))=FFT_n(\sum_{i=0}^k z_i X^i)=(z(1), z(\omega), \dots, z(\omega^{n-1}))$
où $\omega =\exp(\frac{2i\pi}{n})$

$Z(X)=Z_p(X^2) + XZ_i(X^2)$

$FFT_{2n}(Z(X))=FFT_{2n}(Z_p(X^2))+FFT_{2n}(X Z_i(X^2))$

$=(Z_p(1),Z_p(w_{2n}^2),...,Z_p(w_{2n}^{2n})),$
\textbf{À compléter}
Si $f(n)=$ coût de $FFT_n$,

$f(2n)=2f(n)+O(n)$

$\frac{f(2n)}{2n}=\frac{f(n)}{n}+O(1)$

$\frac{f(2^k)}{2^k}=O(k) \Rightarrow f(2^k)=O(k 2^k)$

et $f(n)=O(n log n)$.

\begin{proposition}
$FFT^{-1}=\frac{1}{n}* \overline{FFT}$

$\overline{FFT}=FFT$ avec $\overline{w}=e^{\frac{-2 i \pi}{n}}$
\end{proposition}

Rem: Tout ça marche encore das un corps contenant les racines 2n-ièmes de l'unité. En crypto à base de réseaux, on travaille en général dans $O_{K_n}/p$ avec $p$ choisi de telle sorte qu'on ait suffisammen t de racines de l'unité dans $\mathbb{Z}/p \mathbb{Z}$ ($p$ congru à $1 mod n$). 

Dans ce cas, $w_n \in \mathbb{Z}/p \mathbb{Z}$ et on ne fait que des opérations dans $\mathbb{Z}/p \mathbb{Z}$.
$\Rightarrow O(n log n (log p)^2)$ pour une multiplication.

\section{Chiffrement totalement homomorphe} (Fully Homomorphic Encryption, FHE)

\subsection{Problème}

Construire un système de chiffrement à clé publique KeyGen/Enc/Dec+ une fonction Evaluate telle que 
$\forall f: (\mathbb{Z}/ 2 \mathbb{Z})^n \rightarrow (\mathbb{Z}/ 2 \mathbb{Z})^{n'}$,

$\forall m \in (\mathbb{Z}/ 2 \mathbb{Z})^n | Enc(p_k,m_i)=c_i$,

$Dec(s_k, Evaluate(p_k,f,c_1,...,c_n))=f(m_1,..,m_n)$

Un tel système est dit homomorphe pour $f$ - Il est totalement homomorphe s'il est homomorphe pour tous les $f$.

Ex: RSA homomorphe pour la multiplication modulo $N$.

$f : (\mathbb{Z}/ N \mathbb{Z})*(\mathbb{Z}/ N \mathbb{Z}) \rightarrow (\mathbb{Z}/ n \mathbb{Z})$

$(x,y) \mapsto x y$

$f(RSA(p_k,x),RSA(p_k,y))=RSA(p_k,x) RSA(p_k,y)=(x^e \ mod \ N)(y^e \ mod \ N)=(x y)^e \ mod \ N=RSA(p_k,x y)$

Mais RSA n'est pas totalement homomorphe. Pour être totalement homomorphe, il faut savoir traiter les cas f=XOR, AND.

Exemple trivial: Evaluate = id (paresseuse)
$Dec(s_k,x)=f(Dec(s_k,c_1),....,Dec(s_k,c_n))$.

Pour écarter cet exemple, on demande que la sortie d'Evaluate ne donne aucune info sur $f$.

\textbf{Sécurité}: On veut que le système à clé publique sous-jacent soit sémantiquement sûr.

CCA2 ?

$c=Enc(p_k,m)$

$c'=Evaluate(p_k,+,c,Enc(p_k,m'))$

On donne $c'$ à déchiffrer $\Rightarrow m + m'$

On connait $m'$ $\Rightarrow$ On connaît $m$.

Jamais de sécurité CCA2 dans le cas homomorphe.

\subsection{Un exemple simple, sans réseaux - SWHE = Somewhat Homomorphic}

Principe: Schéma de chiffrement symétrique. Clé $p \in \mathbb{N}$, $2^{\eta-1} \leq p < 2^{\eta}$

Chiffrement: $m \in \{ 0 ; 1 \}$
Choisir $p$, $q$ au hasard.

$c=pq+2 r+m$

Déchiffrement:
$(c \ mod \ p) \ mod \ 2 = m$

Nécessite $r < \frac{p-1}{2}$ (sinon, si $2 r=p+1$, résultat faux)

Correction: 

$2 r + m < p$

$\Rightarrow c \ mod \ p = 2 r + m$

$c \ mod \ p \ mod \ 2 =m$

Variante à clé publique: On publie un grand nombre de valeurs $X_i = p q_i + 2 r_i$, $i \in [1,N]$

Chiffrement: $c=m+ \sum_{i \in I} X_i, I \subset[1,N]$

Déchiffrement: $c \ mod \ p \ mod \ 2$. (ça marche dès que $|I|max r_i < \frac{p-1}{2}$)

Description formelle du schéma:

KeyGen($\lambda$). $s_k =$ entier impair, uniforme, taille $\lambda^2$

$p_k =$ Pour $i$ de $1$ à $2 \lambda^5$.

Tirer $q_i$ aléatoire de $[0, \frac{2 \lambda^5}{p}]$

$r_i$ aléatoire de taille $\lambda$

$X_i \leftarrow p q_i + r_i$

Quitte à réordonner les $X_i$, $X_0$ est le plus grand, est impar, et $X_0 \ mod \ p$ est pair.

Enc: Tirer $S \subset [1, 2 \lambda^5]$. $R$ de taille $2 \lambda$. $c=m+2 R+2 \sum_{i \in S} X_i (mod \ X_0)$

Evaluate: XOR : $add(c_1,c_2) \mod \ X_0$
AND : $mul(c_1,c_2) \ mod \ X_0$

Dec: $c \ mod \ p \ mod \ 2$

\begin{lemma}
$c=a p + 2 b +m$, avec $(2 b +m)\leq 2 \lambda^5 2^{2 \lambda + 3}$
\end{lemma}

$f(c_1,...,c_n)$ congru à $f(2 b_1+m_1,..., 2 b_n+m_n)$ modulo p

Donc si $f(1 b_1+m_1,...,2 b_n+ m_n)<p$ alors

$f(2 b_1+m_1,..,2 b_n + m_n)=f(c_1,...,c_n) \ mod \ p$

$\Rightarrow f(m_1,...,m_n)=f(c_1,...,c_n) \ mod \ p \ mod \ 2$

Idem pour * : Ok par récurrence sur le nombre de portes.

$Dec(s_k,Evaluation(f,c_1,...c_n))=f(m_1,..m_n)$

Si $f(2 b_1+m_1,...,2 b_n+m_n)<p$

$2 b_i + m_i \leq 2 \lambda^5 + 2^{2 \lambda+3}$

Conséquence: On sait évaluer homomorphiquement tous les circuits qui, sur des entrées de taille $\leq 2 \lambda^4 2^{2 \lambda +3}$, produisent un résultat $< 2^{\lambda^2 -1} (x p)$.

Profondeur max autorisée dans des multiplications en cascade : $log_2 \lambda$

\subsection{La "vraie" construction, mais SWHE}

SWHE = Homomorphe pour des circuits "pas trop profonds".

$\lambda$ paramètre de sécurité.

$n=f(\lambda)$, $n$ de la forme $2^k$

$R=O_{K_n}$

(Méta)-Description:

Idéal $Gen(\lambda,R)$ "tire" un idéal de $R$, avec une "bonne" base de $J$

$KeyGen(\lambda,R)$: $J,B_J^{s_k} \leftarrow IdealGen(\lambda,R)$

$B_I$, $I$ un idéal de $R$ tel que $I+J=R$ [I=(2) est un classique]

Clé secrète: $B_J^{s_k}$

Clé publique: $I, B_J^{p_k}=HNF(B_J^{s_k})$

Avec une mauvaise base ($B_J^{p_k}$), je peux calculer des éléments de $J$, mais pas "réduire mod $J$" (au sens résoudre un BDD); je peux en revanche "réduire mod $J$" connaissant $B_J^{s_k}$.

Chiffrement: 
Hypothèse: Je sais encoder mon message en un élément de $P(B_I)$.
Si $I=(2)$, $m \in \{0,1\}[X]/(X^n+1)$

$Samp(x,r_Enc) \rightarrow x+ \rho, \rho \in I, x \in P(B_I), r_Enc \in \mathbb{R}^+$ t.q. $||x+p|| \leq r_Enc$

[Rem. Les ||.|| sont relatives au plongement des coordonnées]

$c=x+\rho mod B_J^{p_k}$

$=x+ \rho - B_J^{p_k} *(Roundoff de (B_J^{p_k-1}(x+ \rho)))$ (méthode Roundoff pour trouver un vecteur proche de $x + \rho$ dans $J$).

Comme $B_J^{p_k}$ est une mauvaise base, $B_J^{p_k} Roundoff(B_J^{p_k-1} (x+ \rho))$ est presque un élément aléatoire de $J$ (C'est le $p q$ de tout à l'heure)

Par rapport au système simple,

\begin{itemize}
\item On peut calculer directement des éléments de $J$ connaissant $p_k$, alors qu'on ne pouvait pas calculer des mult. de $p$.
\item Pourquoi : La donnée de p permettait de déduire $mod \ p$. Dans le cas des réseaux, on peut se donner le réseau (via une mauvaise base) sans se donner la possibilité de réduire modulo le réseau (ce qui nécessite une bonne base !)
\end{itemize}

Déchiffrement: $c \ mod \ B_J^{s_k} \ mod \ B_I$

Evaluate: $(p_k,c_1,..)$

$Add(c_1,c_2)=c_1+c_2 \ mod \ B_j^{p_k}$

$Mult(c_1,c_2)=c_1 c_2 \ mod \ B_j^{p_k}$

Correction: À quelle condition déchiffre-t-on correctement ?

$c=m+\rho+j$, $j \in J$

\begin{theorem}
Ce message est déchiffré correctement si $m+p \in P(B_J^{s_k})$;
Pour ce faire, il suffit que $||m+p|| < r_Dec$, où

$r_{Dec}$ est le rayon de la plus grande boule $\leq P(B_J^{s_k})$
\end{theorem}

\begin{proof}
$x mod B_J^{s_k}$

$x = x - B_J^{s_k} [(B_J^{s_k})^{-1} x]$

Quelles sont les coordonnées de $x \ mod \ B_J^{s_k}$ dans la base $B_J^{s_k}$ ?

$(B_J^{s_k})^{-1}. (x \ mod \ B_J^{s_k})$

$= (B_J^{s_k})^{-1} x - Roundoff((B_J^{s_k})^{-1})$

$\in [- \frac{1}{2},\frac{1}{2}[$

$\Rightarrow x mod B_J^{s_k}= B_J^{s_k}.([- \frac{1}{2},\frac{1}{2}[^n)=P(B_J^{s_k})$

$c \ mod \ B_J^{s_k}=m+\rho+j$, $j \in J$

et $c mod B_J^{s_k} \in P(B_J^{s_k})$

Conséquence: si $m+\rho \in P(B_J^{s_k})$,

$m+\rho = c \ ,mod \ B_J^{s_k}$

Par le même argument, $m * \rho \ mod \ B_I = m$
\end{proof}

\begin{proposition}
$B^* := (^t B_j^{s_k})^{-1}$
Alors $r_{Dec}= \frac{1}{2 ||| B |||}$, où $|||M|||= sup ||$colonnes de M$||$
\end{proposition}

\begin{proof}
Soit $\rho \in P(B_J^{s_k})$
$\Leftrightarrow (B_J^{s_k})^{-1} \rho$ a toutes ses coordonnées dans $[- \frac{1}{2},\frac{1}{2}]$

$\Leftrightarrow ||(B_J^{s_k})^{-1} \rho||_{infinity} < \frac{1}{2}$.

$(B_J^{s_k})^{-1}=(<\gamma_i,\rho>)$, où les $\gamma_i$ sont les colonnes de $B^*$

Cauchy-Schwarz:

$\Rightarrow ||B_J^{-1} \rho||_{infinity} \leq (sup || \gamma_i ||) ||\rho||$.

En particulier, si $||\rho|| < \frac{1}{2} ||| B^* ||| \Rightarrow ||(B_J^{s_k})^{-1}||_{infinity} < \frac{1}{2}$

$\rightarrow \rho \in P(B_J^{s_k})$.

Inversement, si $||\gamma_j||= sup_{1 \leq i \leq n} ||\gamma_i||$, alors $\rho=\frac{1}{2} \gamma_j$ vérifie $|| \rho || = \frac{1}{2} |||B^*|||$ et $\rho \not\in P(B_J^*)$ car sa $j^{ème}$ coordonnée dans cette base vaut $\frac{1}{2}$
\end{proof}

\textbf{Dessin !!!! Cf Hugo Feree}

Idéalement, on veut $r_{Dec}$ le plus grand possible.

$r_{Dec} \leq \frac{\lambda_1(L)}{2}$

\begin{proposition}
$r_{Dec}$ peut être pris $= \frac{\lambda_1(L)}{O(1)}$
\end{proposition}

\begin{proof}
On considère $t \in \mathbb{N}$

$V= t e_1 + \sigma_1$, $\sigma \in B(0,s)$

$B_J^{s_k}=(X^i V)=(Rot^i(V))$

$V_i=Rot^i(V)$

$a \in \mathfrak{d} P(B_J^{s_k})$

Alors $a=\sum \alpha_i v_i$ avec un des $\alpha_i=^+_- \frac{1}{2}$

$=^+_- \frac{1}{2} v_i + \sum_{j \neq i} \alpha_j v_j$, $\alpha_j \in [-\frac{1}{2},\frac{1}{2}]$

$(a,e_i)=^+_- \frac{1}{2}(v_i,e_i)+ \sum_{j  \neq i} \alpha_j (v_j,e_i)$

$|(v_i,e_i)| \geq t-s$ 

$|(v_j,e_i)| \leq s \Rightarrow |(a,e_i)| \geq \frac{1}{2} (t-s)- \frac{1}{2}(n-1)s$

$\geq \frac{1}{2} (t-n s)$

$||a||^2=\sum_{j=1}^n <a,e_j>^2 \geq <a,e_i>^2 \geq \frac{1}{4}(t-n s)^2$

$||a|| \geq \frac{1}{2} (t-n s)$

$r_{Dec} \geq \frac{1}{2} (t - n s)$ (En prenant $n s$ de l'ordre de $\frac{t}{2}$, on trouve $r_{Dec}$ de l'ordre de $\frac{t}{4}$, $\lambda_1(L)$ de l'ordre de $\frac{3 t}{2}$)

$\lambda_1(L) \leq ||v||$ de l'ordre de $t+ n s$
\end{proof}

%% $r_Enc \leq ||m+\rho||$

Les portes Add et Mult sont l'addition et la multiplication de $R/I$.

Dans le cas $I=(2)$.

$R/I$ isomorphe à $\mathbb{Z}/2 \mathbb{Z}$ (en tant que groupe).

Add= addition bit à bit
Mult = ?!

On s'en sort en disant que le message de départ est $m \in \{0 ; 1 \}$

Dans ce cas, mult sur $R/I$ est un simple Et.

Et si $I \neq (2)$, $m \in \{ 0 ; 1 \}$
Mult = $m_1 . m_2$ avec $.$ la multiplication dans $R/I$
Not = $1-m_1$ avec $-$ l'addition dans $R/I$.

\subsubsection{Limites sur le circuit évaluable}

\begin{theorem}
$C$ un polynôme en $t$ variables, de degré total $d$. L'évaluation de $C$ de façon homomorphe est possible si
$\gamma_X^{d-1} ||C||_1 r_{Enc}^d < r_{Dec}$

En particulier, si $C$ a des coefficients $\{ 0 ; 1\}$, le circuit est licite si

$d \leq \frac{log r_{Dec}}{log \gamma_X^{d-1} (t-1) r_{Enc}}$

où $\gamma_X = max_{u, v \in R} \frac{||u v||}{||u|| ||v||}=\sqrt{n}$ si $R= \mathbb{Z}[X]/(X^n +1)$ ($n=2^k$)
\end{theorem}

\begin{proof}
Supposons qu'on évalue de façon homomorphe $C(x_1,...,x_n)$.

$x_i$ (flèche bizarre) $ x_i + \rho_i$ (où $\rho_i \in I$) (flèche bizarre) $x_i + \rho_i + j_i$ (où $j_i \in J$).

On vérifie par induction sur la structure du circuit, utilisant, qu'on calcule en réalité  $C(x_1+i_1,...,x_n+i_n)+j$, $j \in J$.

Dès que $||C(x_1+i_1,...,x_n+i_n)|| < r_{Dec}$, $(*')$

on a $Dec(s_k,C(x_1+i_1,...,x_n+i_n)+j)=C(x_1+i_1,....,x_n+i_n) mod \ B_I$ (par déf de $r_{Dec}$)

$C(x_1+i_1,...,x_n+i_n)=C(x_1,...,x_n) mod \ B_I$

et le résultat de Evaluate $(p_k, C, Enc(p_k,x_1),...,Enc(p_k,x_n))$ se déchiffre bien en $C(x_1,...,x_n) mod \ B_I$: on évalue correctement les circuits polynomiaux mod $B_I$ vérifiant $(*')$.

$||C(x_1,...,x_n)||< ?$

$C-u_1,...,u_n)= \sum_{\sum \alpha_i \leq d} C_{\alpha_1,...,\alpha_n} u_1^{\alpha_1}... u_n^{\alpha_n}$

$||C(u_1,...,u_n)|| \leq \sum C_{\alpha_1,...,\alpha_n} || u_1^{\alpha_1}... u_n^{\alpha_n}|| \leq \sum C_{\alpha_1,...,\alpha_n}  \gamma_X^{d-1}$

\textbf{À compléter}

Pour $u_i = x_i + \rho_i$, $||u_i||< r_{Enc}$, d'où $||C(x_1+i_1,...,x_n+i_n) ||< ||C||_1 \gamma_X^{d-1} r_{Enc}^d$ et le calcul est correct dès que ceci est $< r_{Dec}$.

Si $C$ est à coeffs $\{0;1 \}$, $||C||_1 \leq (t+1)^d$

$\gamma_X = \sqrt{n} ?$

$u.v = (^+_- u_i v_{n+j-i mod \ n})_{0 \leq j \ n-i}$

Chacun des termes du vecteur sont $\leq ||u|| ||v||$ par Cauchy-Schwarz, donc $||u v||^2= \sum(termes)^2 \leq n||u||^2 ||v||^2$
\end{proof}

\subsubsection{Analyse de sécurité}

Attaquer le schéma: étant donné $x + \rho mod B_J^{p_k}$, trouver $x+\rho$ sachant que $||x+\rho|| < r_{Enc}$

$\Leftrightarrow$ étant donné $x+\rho+j, j \in J$, trouver $j$, $d(x+\rho+j,J)< r_{Enc}$

BDD (bounded distance decoding)

Ideal-BDDP:

$Samp_1(r)$: renvoie $r \in R$

$b \leftarrow \{0;1 \}$, $(B_J^{s_k},B_J^{p_k}) \leftarrow IdealGen$ (comme dans système de chiffrement)

Si $b=0$, $r \leftarrow Samp_1(R), t \leftarrow r mod B_J^{p_k}$

Si $b=1$, $t=Unif (R mod B_J^{p_k})$

Étant donné t, l'attaquant doit deviner $b$.

Principe: 

Attaquer I-BDD, c'est savoir distinguer entre:
\begin{itemize}
\item Un élément proche de $J$ (cas $b=0$, chiffré de $0$)
\item Un élément aléatoire $mod$ $J$ (cas $b=1$)
\end{itemize}

\begin{theorem}
Si on sait attaquer la sécurité sémantique du système SWHE avec avantage $\epsilon$ (et $I=(s), \rho=s. Samp_1(R)$), alors on sait attaquer Ideal-BDDP aavec avantage $\geq \frac{ \epsilon}{2}$ et la même complexité.
\end{theorem}

\begin{proof}
Idée : Je suppose que j'ai un oracle O pour attaquer la sécurité sémantique de mon système.

Je reçois un défi $t$ pour I-BDDP.

L'oracle, étant donné $m_0, m_1$,

$Enc(p_k, m_{\beta}) \rightarrow \beta$ avec avantage $\epsilon$.


$m_{\beta}+t s mod \ B_J^{p_k}$ est : du bruit si $b=1$, le chiffré de $m_{\beta}$ si $b=0$

J'envoie $m_{\beta}+ t s mod \ B_J^{s_k}$ à mon oracle

\begin{itemize}
\item si $b=0$, l'oracle répond $\beta'=\beta$ avec avantage $\epsilon$
\item si $b=1$, l'oracle répond $0$ ou $1$ avec probabilité $\frac{1}{2}$
\end{itemize}

Je réponds $0$ si $\beta = \beta'$, $1$ si $\beta \neq B'$ au défi IBDDP.

Mon avantage est $\epsilon$ quand $b=0$, $0$ quand $b=1$,

donc surtout $\epsilon * \frac{1}{2}+ 0* \frac{1}{2}= \frac{\epsilon}{2}$

\end{proof}

\subsubsection{Choix de paramètres}

$r_{Enc}, r_{Dec}$

Difficulté de BDD:

"rule of thumb": approcher CVP, SVP ou BDD en dim. $n$ à un facteur $2^k$ coûte $2^{\frac{n}{k}}$

Ici, le facteur d'approximation de BDD est $\frac{\lambda_1(J)}{||Samp_1(R)||}$ qui est de l'ordre de $r_{Enc}$ et $r_{Dec}$ ($||r||$, avec $r_{Enc}=||m+r s||$ avec $m \in \{0 ; 1 \}$)($s=2$ pour $I=(2)$)

Le choix $r_{Enc}$ polynômial en n, $r_{Dec}$ de l'ordre de $\lambda_1(J)$, donc en $2^{O(\sqrt{n})}$ donne un facteur d'approximation $2^{O(\sqrt{n})}$, donc une difficulté $2^{O(\sqrt{n})}$.

Taille des circuits évaluables de l'ordre de $\frac{1}{2} log n$

\subsubsection{Une optimisation}

Principe: Remplacer la clé secrète $B_J^{s_k}$ par un vecteur court $v_J^{s_k}$ de $J^{-1}$

Dec: $(c-(v_J^{s_k})^{-1}. Roundoff(v_J^{s_k})) mod \ B_I$

Principe: correct si $J^{-1}$ est principal, engendré par $v_J^{s_k}$; dans ce cas, $J$ est principal, engendré par $(v_J^{s_k})^{-1}$, et calculer $(v_J^{s_k})^{-1}. Roundoff(v_J^{s_k})$ est identique à calculer $(B_J^{s_k})^{-1}. Roundoff(v_J^{s_k})$ où $B_J^{s_k}=(v_J^{s_k},Rot(v_J^{s_k}),....,Rtot^{n-1}(v_J^{s_k}))$

(bonne base)

Si $J^{-1}$ n'est pas principal, comme $v_J^{s_k} \in J^{-1}$, $<v_J^{s_k}> \subset J^{-1} \Leftrightarrow J \subset <(v_J^{s_k})^{-1}>$

On réduit modulo un réseau plus dense qui correspond au parallélogramme fondamental du réseau engendré par $(v_J^{s_k})^{-1}$. On peut montrer qu'on peut toujours choisir $v_J^{s_k}/ r_{Dec} = r_{Dec}/poly(n)$

\subsection{Comment transformer SWHE+bootstrappable (réinitialisable) en FHE}

Un schéma SWHE (sachant évaluer des circuits "pas trop gros") qui sait évaluer un circuit composé d'une porte $\and$ ou $\oplus$ et de son propre circuit de déchiffrement peut être rendu FHE.

On dit qu'il est réinitialisable.

Principe:

\begin{itemize}
\item Quand on fait trop de calculs, on introduit trop de bruit (de l'ordre de $r_{Dec}$ (grand))
\item Il faut rafraîchir les chiffrés, ie déchiffrer+rechiffrer (bruit redevient de l'ordre de $r_{Enc}$ (petit))
\item En l'état: pas pratique
\end{itemize}

En revanche, on peut exécuter le circuit de déchiffrement de façon homomorphe.

Recrypt:Nouveau couple $(pk_2,sk_2)$.
$C=$Evaluate$(p_k,f,C_i)$
$s_k'=$Enc$(pk_2,s_k)$

$C'=Enc(pk_2,C)$

$C''=$Evaluate$(pk_2,Dec,s_k',C')$

\begin{proposition}
$Dec(sk_2,C'')=Dec(s_k,C)=f(m_1,...m_n)$ (en ignorant les problèmes de bruit)
\end{proposition}

\begin{proof}
$Dec(sk_2,C'')=Dec(sk_2,Evaluate(pk_2,Dec,s_k',C'))=Dec(Dec(sk_2,s_k'),Dec(sk_2,C'))=Dec(s_k,C)=Dec(s_k,Evaluate(p_k,f,c_1,...,c_n))=f(m_1,...,m_n)$
\end{proof}

Si le schéma est réinitialisable, par hypothèse le calcul est licite, ie ça marche effectivement malgré les aspects "bruit", et on peut encore évaluer une porte logique ur le résultat tout en gardant la validité du déchiffrement.

On obtient un schéma FHE en faisant Recrypt après chaque porte logique.

Problème (ouvert): le schéma de chiffrement/déchiffrement tel que présenté n'est pas réinitialisable, le déchiffrement coûte trop cher.

Compacter le déchiffrement: Idée: Soulager le circuit de déchiffrement d'une partie du calcul.

Difficulté: Imaginer que tout est fait dans le monde homomorphe. ($\Rightarrow$ pas de tests !)

On va inclure dans la clé publique des indices sur la clé secrète qui permettent d'accélérer le déchiffrement.

$KeyGen^*(\lambda)$
$(s_k,p_k) \leftarrow KeyGen(\lambda)$
$(s_k^*,\tau) \leftarrow SplitKey(s_k,p_k)$

Clé publique: $(p_k,\tau)$
Clé secrète: $s_k^*$

$Enc^*: c \leftarrow Enc(p_k,m)$
$c^* \leftarrow (c,Expand CT(p_k,c))$

$Add^*$ : $(Add(c_1,c_2),Expand CT(p_k, Add(c_1,c_2)))$
$Mult^*$ : Idem

Splitkey($s_k$):
$\tau=$ensemble $\{ t_1,...,t_{\gamma_s(n)} \}$, $t_i$ uniformes dans $J^{-1} mod \ B_I$, tel qu'il existe un ensemble $S$ de taille $\gamma_{ss(n)}$ avec

$\sum_{i \in S} t_i= v_J^{s_k} mod \ I$ ($v_J^{s_k}$= vecteur court de $J^{-1}$)

$s_k^*=(M)_{\gamma_{ss} \gamma_s}$ $M_{i,j}=1$ si $j$ est le $i^{ème}$ élément de $S$, $0$ sinon. 

Par exemple, $t_1,...,t_{\gamma_s(n)-1}$ au hasard uniformément, choisir $S'$ de cardinal $\gamma_{ss(n)}-1$ et
$t_{\gamma_{s(n)}}=v_J^{s_k} - \sum_{i \in S'} t_i$, $S=S' \cup \{ \gamma_S(n) \}$

On repermute les $t_i$.

ExpandCT($p_k,c$)

renvoyer $c_i=t_i c mod \ B_I$, $i=1... \gamma_S(n)$

Idée: $\sum_{i \in S} c_i = \sum_{i \in S} t_i c= c \sum_{i \in S} t_i=c b_J^{p_k}$

On veut calculer Roundoff($\sum_{i \in S} c_i$)

$(X_i) \leftarrow (1....1)M(c_j)$

$X \leftarrow Roundoff(\sum X_i)$

C'est un morceau du circuit de déchiffrement, qu'il faut exécuter de façon homomorphe.

$y_1,...,y_n \in \{0;1\}$

$y_1+...+y_n=\overline{z_1...z_k}$ où $z_i=poly(y_1,...,y_n)$

\begin{lemma}
$e_i(y_1,...,y_n)$ le $i^eme$ polnôme symétrique élémentaire en $y_1,...,y_n$.

Alors le développement binaire de $y_1+...+y_n$ est $e_{2^k} (y_1,...y_n) mod \ 2$
\end{lemma}

\begin{proof}
Si $w$ termes $x_i$ sont $=1$.

$e_{2^k}(x_1,...,x_n)=(2^k parmi w) (mod 2)$
\end{proof}

\begin{lemma}
La plus grande puissance de $2$ divisant $n!= \sum_{j=1}^{infini} \lfloor \frac{n}{2 ^{\gamma}} \rfloor$
\end{lemma}

\begin{proof}
\end{proof}

\subsection{Comment rendre la solution de 3 réinitialisable}
